package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
//
// 
//
// 示例 1： 
//
// 输入：[-4,-1,0,3,10]
//输出：[0,1,9,16,100]
// 
//
// 示例 2： 
//
// 输入：[-7,-3,2,3,11]
//输出：[4,9,9,49,121]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 10000 
// -10000 <= A[i] <= 10000 
// A 已按非递减顺序排序。 
// 
// Related Topics 数组 双指针 
// 👍 153 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution977 {
    //排序法：流式计算
    /*public static int[] sortedSquares(int[] A) {
        return Arrays.stream(A).map(x -> x * x).sorted().toArray();
    }*/

    /**
     * 双指针法：
     * 数组其实是有序的,数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
     * 此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
     **/
    public static int[] sortedSquares(int[] A) {
        int i = 0, j = A.length - 1;
        int tmp[] = new int[A.length];
        int tmpIndex = j;
        while (i != j) {
            if (A[j] * A[j] > A[i] * A[i]) {
                tmp[tmpIndex--] = A[j] * A[j];
                j--;
            } else {
                tmp[tmpIndex--] = A[i] * A[i];
                i++;
            }
        }
        tmp[0] = A[i] * A[i];
        for (int i1 = 0; i1 < A.length; i1++) {
            A[i1] = tmp[i1];
        }
        return A;
    }

    public static void main(String[] args) {
        int nums[] = new int[]{-4, -1, 0, 3, 10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
